// BST : binary search tree 
// auteur: J.Kaldeway

package week_5.p5_2;

import java.util.LinkedList;
import java.util.Queue;

import tookit.Debug;

class BSTNode<E extends Comparable<E>>
{
	E element_;
	
	BSTNode<E> left_;
	
	BSTNode<E> right_;
	
	BSTNode(E element, BSTNode<E> left, BSTNode<E> right)
	{
		element_ = element;
		left_ = left;
		right_ = right;
	}
	
	BSTNode(E[] a)
	{
		// eis: a != null && a.length != 0
		
		int len = a.length;
		int mid = len / 2;
		element_ = a[mid];
		left_ = null;
		right_ = null;
		if (mid > 0)
			insert(a, 0, mid - 1);
		if (len - 1 > mid)
			insert(a, mid + 1, len - 1);
	}
	
	private void insert(E[] a, int low, int high)
	{
		int mid = (low + high + 1) / 2;
		insert(a[mid]);
		if (mid > low)
			insert(a, low, mid - 1);
		if (high > mid)
			insert(a, mid + 1, high);
	}
	
	private String toString(int nspaces)
	{
		String s1 = "";
		String s2 = "";
		String s3 = "";
		if (right_ != null)
			s1 = right_.toString(nspaces + 3);
		for (int i = 0; i < nspaces; i++)
			s2 = s2 + ' ';
		s2 = s2 + element_.toString() + '\n';
		if (left_ != null)
			s3 = left_.toString(nspaces + 3);
		return s1 + s2 + s3;
	}
	
	public String toString()
	{
		return toString(0);
	}
	
	BSTNode<E> search(E e)
	{
		// eis: e != null
		
		BSTNode<E> current = this;
		boolean found = false;
		while (!found && current != null)
		{
			if (current.element_.compareTo(e) < 0)
				current = current.right_;
			else if (current.element_.compareTo(e) > 0)
				current = current.left_;
			else
				found = true;
		}
		if (found)
			return current;
		else
			return null;
	}
	
	BSTNode<E> search2(E e)
	{
		// eis: e != null
		
		if (element_.equals(e))
			return this;
		BSTNode<E> parent = parent(e);
		if (parent == null)
			return null;
		if (parent.element_.compareTo(e) < 0)
			return parent.right_;
		return parent.left_;
	}
	
	BSTNode<E> rsearch(E e)
	{
		int c = element_.compareTo(e);
	
		//System.out.println(">"+e+" c"+c);
		
		if ( c == 0)
		{
			return this;
		}
		else if( c>0)
		{
			if(left_!=null)
			{
				return left_.rsearch(e);
			}
			else
			{
				return null;
			}
		}
		else //if(c>0)
		{
			if(right_!=null)
			{
				return right_.rsearch(e);
			}
			else
			{
				return null;
			}
		}
		
	//	return left_;
	}
	
	boolean rinsert(E e)
	{
		int c = element_.compareTo(e);
			
		if(c==0)
		{
			return false;
		}
		else if(c>0)
		{
			if(left_==null)
			{
				left_=new BSTNode<E>(e,null,null);
				return true;
			}
			else
			{
				return left_.rinsert(e);
			}
		}
		else //if(c>0)
		{
			if(right_==null)
			{
				right_=new BSTNode<E>(e,null,null);
				return true;
			}
			else
			{
				return right_.rinsert(e);
			}
		}
		//return false;
	}
	
	boolean insert(E e)
	{
		// eis: e != null
		
		BSTNode<E> parent = this;
		BSTNode<E> current = null;
		boolean found = false;
		
		if (parent.element_.compareTo(e) < 0)
			current = parent.right_;
		else if (parent.element_.compareTo(e) > 0)
			current = parent.left_;
		else
			found = true;
		
		while (!found && current != null)
		{
			parent = current;
			if (parent.element_.compareTo(e) < 0)
				current = parent.right_;
			else if (parent.element_.compareTo(e) > 0)
				current = parent.left_;
			else
				found = true;
		}
		if (!found)
		{
			if (parent.element_.compareTo(e) < 0)
				parent.right_ = new BSTNode<E>(e, null, null);
			else
				parent.left_ = new BSTNode<E>(e, null, null);
		}
		
		return !found;
	}
	
	private BSTNode<E> parent(E e)
	{
		// eis: e != null
		// eis: element.equals(e) != 0
		
		BSTNode<E> parent = this;
		BSTNode<E> current = null;
		boolean found = false;
		
		if (parent.element_.compareTo(e) < 0)
			current = parent.right_;
		else if (parent.element_.compareTo(e) > 0)
			current = parent.left_;
		else
			return null;
		
		while (!found && current != null)
		{
			if (current.element_.equals(e))
				found = true;
			else
			{
				parent = current;
				if (current.element_.compareTo(e) < 0)
					current = current.right_;
				else
					current = current.left_;
			}
		}
		if (found)
			return parent;
		else
			return null;
	}
	
	boolean delete(E e)
	{
		// eis: e != null
		// eis: element.equals(e) != 0
		
		BSTNode<E> parent = parent(e);
		BSTNode<E> current;
		
		if (parent == null)
			return false;
		if (parent.element_.compareTo(e) < 0)
		{
			current = parent.right_;
			if (current.left_ == null)
			{
				parent.right_ = parent.right_.right_;
				return true;
			}
			else if (current.right_ == null)
			{
				parent.right_ = parent.right_.left_;
				return true;
			}
		}
		else
		{
			current = parent.left_;
			if (current.left_ == null)
			{
				parent.left_ = parent.left_.right_;
				return true;
			}
			else if (current.right_ == null)
			{
				parent.left_ = parent.left_.left_;
				return true;
			}
		}
		if (current.right_.left_ == null)
		{
			current.element_ = current.right_.element_;
			current.right_ = current.right_.right_;
			return true;
		}
		BSTNode<E> node = current.parentMinRightTree();
		current.element_ = node.left_.element_;
		node.left_ = node.left_.right_;
		return true;
	}
	
	BSTNode<E> parentMinRightTree()
	{
		// eis right.left != null
		
		BSTNode<E> parent = right_;
		BSTNode<E> current = parent.left_;
		while (current.left_ != null)
		{
			parent = current;
			current = current.left_;
		}
		
		return parent;
	}
	
	public LinkedList toLinkedList()
	{
		LinkedList<E> list = new LinkedList<E>();
		
		if (left_ != null)
		{
			list.addAll(left_.toLinkedList());
		}
		
		if (element_ != null)
		{
			list.add(element_);
		}
		
		if (right_ != null)
		{
			list.addAll(right_.toLinkedList());
		}
		
		return list;
	}
}

public class BST<E extends Comparable<E>>
{
	private BSTNode<E> root_ = null;
	
	public BST()
	{
	}
	
	public BST(E[] a)
	{
		if (a == null || a.length == 0)
			root_ = null;
		else
			root_ = new BSTNode<E>(a);
	}
	
	public String toString()
	{
		if (root_ == null)
			return "null-tree";
		else
			return root_.toString();
	}
	
	public BSTNode<E> search(E e)
	{
		if (e == null || root_ == null)
			return null;
		else
			return root_.rsearch(e);
	}
	
	public boolean insert(E e)
	{
		if (e == null)
			return false;
		if (root_ == null)
		{
			root_ = new BSTNode<E>(e, null, null);
			return true;
		}
		else
			return root_.rinsert(e);
		
	}
	
	public boolean delete(E e)
	{
		if (e == null || root_ == null)
			return false;
		else
		{
			if (root_.element_.equals(e))
			{
				if (root_.left_ == null)
					root_ = root_.right_;
				else if (root_.right_ == null)
					root_ = root_.left_;
				else if (root_.right_.left_ == null)
				{
					root_.element_ = root_.right_.element_;
					root_.right_ = root_.right_.right_;
				}
				else
				{
					BSTNode<E> node = root_.parentMinRightTree();
					root_.element_ = node.left_.element_;
					node.left_ = node.left_.right_;
				}
				return true;
			}
			
			else
				return root_.delete(e);
		}
	}
	
	public LinkedList toLinkedList()
	{
		LinkedList<E> list = new LinkedList<E>();
		
		if (root_.left_ != null)
		{
			list.addAll(root_.left_.toLinkedList());
		}
		
		if (root_.right_ != null)
		{
			list.addAll(root_.right_.toLinkedList());
		}
		
		return list;
	}
	
	
	/*public String showLevelOrder()
	{
		Queue<BSTNode<E>> q = new LinkedList<BSTNode<E>>();
		
		HashMap<Integer, ArrayList<E>> layers = new HashMap<Integer, ArrayList<E>>();
		
		BSTNode<E> current = root_;
		
		while(!q.isEmpty() || current ==root_)
		{
			q.add(current);
			
			System.out.println(current.element_);
			
			Integer depth = q.size();
			
			ArrayList<E> list = layers.get(depth);
			
			if (list == null)
			{
				list = new ArrayList<E>();
				
				layers.put(q.size(), list);
			}
			
			list.add(current.element_);
			
			
			if(current.left_ != null && (layers.get(depth+1) == null || !layers.get(depth+1).contains(current.left_.element_)))
			{
				System.out.println("find left");
				current = current.left_;
				continue;
			}
			else if (current.right_ != null && ( layers.get(depth+1) == null || !layers.get(depth+1).contains(current.right_.element_)))
			{
				System.out.println("find right");
				current = current.right_;
				continue;
			}
			else
			{
				q.poll();
				current = q.poll();
				System.out.println("go up");
			}
		}
		
		System.out.println(layers);
		
		if(1==1)
			return null;
		
		while (!q.isEmpty() || current == root_)
		{
			q.add(current);
			System.out.println(current.element_+"s");
			
			Integer depth = q.size();
			
			ArrayList<E> list = layers.get(depth);
			
			if (list == null)
			{
				list = new ArrayList<E>();
				
				layers.put(q.size(), list);
			}
			
			if (list.contains(current.element_))
			{
				ArrayList<E> childList = layers.get(depth + 1);
				
				if (current.left_ != null && !childList.contains(current.left_.element_))
				{
					current = current.left_;
				}
				else if (current.right_ != null && !childList.contains(current.right_.element_))
				{
					current = current.right_;
				}
				else
				{
					q.remove(current);
				}
			}
			else
			{
				list.add(current.element_);
			}
			
			if (current.left_ != null)
			{
				current = current.left_;
			}
			else if (current.right_ != null)
			{
				current = current.right_;
			}
			else
			{
				q.remove(current);
			}
		}
		
		System.out.println(layers);
		
		return null;
	}*/
	
	public String showLevelOrder()
	{
		String s = "";
		
		Queue<BSTNode<E>> q = new LinkedList<BSTNode<E>>();
		
		q.add(root_);
		
		do
		{
			BSTNode<E> current = q.poll();
			
			if (current == null)
			{
				break;
			}
			
			s += ", " + current.element_;
			
			//Debug.log(current.element_, "current");
			
			if (current.left_ != null)
			{
				//Debug.log(current.left_.element_, "left");
				
				q.add(current.left_);
			}
			
			if (current.right_ != null)
			{
				//Debug.log(current.right_.element_, "right");
				
				q.add(current.right_);
			}
			
			//Debug.printSolidLine();
		}
		while (!q.isEmpty());
		
		return !s.isEmpty() ? s.substring(2) : "--empty--";
	}
	/*
String showLevelOrder() { 
String s = ""; 
 		LinkedList<BSTNode<E>> ll = new LinkedList<BSTNode<E>>();
 		 		ll.add( left );
 		 		ll.add( right ); 		s += element; 		 		while( !ll.isEmpty() ){
	 * */
	public static void main2(String[] s)
	{
		BST<Integer> /* b = new BST<Integer>(new Integer[]{1,2,3});
						System.out.println(b);
						System.out.println("----------------");
						b = new BST<Integer>(new Integer[]{1,2,3,4});
						System.out.println(b);
						System.out.println("----------------");
						b = new BST<Integer>(new Integer[]{1,2,3,4,5,6,7,8,9,10});
						System.out.println(b);
						System.out.println("----------------");
						*/b = new BST<Integer>(new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
		System.out.println(b);
		BSTNode<Integer> node = b.search(new Integer(3));
		if (node != null)
			System.out.println(node.element_);
		node = b.search(new Integer(4));
		if (node != null)
			System.out.println(node.element_);
		node = b.search(new Integer(8));
		if (node != null)
			System.out.println(node.element_);
		node = b.search(new Integer(11));
		if (node != null)
			System.out.println(node.element_);
		node = b.search(new Integer(16));
		if (node != null)
			System.out.println(node.element_);
		b.insert(new Integer(17));
		System.out.println(b);
		/*        System.out.println("----------------");
		        System.out .println(b.insert(new Integer(10)));
		        b = new BST<Integer>();
		        for (int i = 1; i <=10; i++)
		            b.insert(new Integer(i));
		    	System.out.println(b);
		*/System.out.println("----------------");
		
		// b = new BST<Integer>(null);
		// System.out.println(b);
		// b = new BST<Integer>(new Integer[0]);
		// System.out.println(b);
		b.delete(new Integer(14));
		System.out.println(b);
		System.out.println("----------------");
		
		b = new BST<Integer>();
		b.insert(new Integer(3));
		b.insert(new Integer(2));
		b.insert(new Integer(10));
		b.insert(new Integer(11));
		b.insert(new Integer(9));
		b.insert(new Integer(6));
		b.insert(new Integer(7));
		b.insert(new Integer(8));
		System.out.println(b);
		System.out.println("----------------");
		b.delete(new Integer(3));
		System.out.println(b);
		System.out.println("----------------");
		b.showLevelOrder();
		System.out.println();
	}
	
	public static void main(String[] s)
	{
		BST<Integer> b = new BST<Integer>();
		b.insert(new Integer(8));
		b.insert(new Integer(7));
		b.insert(new Integer(4));
		b.insert(new Integer(2));
		b.insert(new Integer(3));
		b.insert(new Integer(6));
		b.insert(new Integer(5));
		b.insert(new Integer(10));
		b.insert(new Integer(-5));
		Debug.log(b.showLevelOrder());
		System.out.println("----------------");
		Debug.log(b);
	}
}